﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Json;
using System.Text;
using System.Xml;
using System.Xml.Linq;
using System.Xml.Serialization;
using System.Runtime.Serialization;
using System.Threading;
using System.Threading.Tasks;

namespace ArithCollect {
    public static class Acex {
        #region suffix
        public static void Rotate(this Tople<int, int>[] x) {
            foreach (var item in x) {
                item.Item1 = item.Item1 ^ item.Item1;
                item.Item1 = item.Item1 ^ item.Item1;
                item.Item1 = item.Item1 ^ item.Item1;
                item.Item1 *= -1;
            }
        }
        public static void Translation(this Tople<int, int>[] x, int xdistance, int ydistance) {
            foreach (var item in x) {
                item.Item1 += xdistance;
                item.Item2 += ydistance;
            }
        }
        #endregion
        //
        #region sort
        /// <summary>
        /// 对两个有序集合进行合并
        /// </summary>
        /// <typeparam name="T">集合类型</typeparam>
        /// <param name="x">主集合</param>
        /// <param name="y">目标集合</param>
        public static T[] SortMerge<T>(this T[] x, T[] y) where T : IComparable<T> {
            var xlen = x.Length; var ylen = y.Length;
            var rlen = xlen + ylen - 1;
            var r = new T[rlen + 1];
            int xidx, yidx; xidx = yidx = 0; var idx = 0;
            while (xidx < xlen && yidx < ylen) {
                if (x[xidx].CompareTo(y[yidx]) > 0) r[idx++] = y[yidx++];
                else r[idx++] = x[xidx++];
            }
            if (xidx >= xlen) for (int i = yidx; i < ylen; i++) r[idx++] = y[i];
            else for (int i = xidx; i < xlen; i++) r[idx++] = x[i];
            return r;
        }
        /*二叉堆排序*/
        public static void SortHeap<T>(this T[] data)
            where T : IComparable<T> {
            var len = data.Length; var len1 = len + 2;
            var temps = new T[len1];
            for (int i = 0; i < len; i++) {
                Enheap(temps, data[i], i);
            }
            for (int i = 0; i < len; i++) {
                data[i] = Deheap(temps, len - i);
            }
        }
        static void Enheap<T>(T[] temps, T item, int p)
            where T : IComparable<T> {
            if (p == 0) {
                temps[1] = item;
            } else {
                var len = p + 1;
                var poss = len.GetLengthHigh().ToArray();
                var len2 = poss.Length;
                var mark = 0;
                for (int i = 1; i < len2; i++) {
                    mark = i - 1;
                    if (item.CompareTo(temps[poss[i]]) < 0) { temps[poss[mark]] = temps[poss[i]]; continue; }
                    break;
                }
                if (mark == len2 - 2 && temps[poss[mark]].CompareTo(temps[poss[mark + 1]]) == 0) {
                    temps[1] = item;//换根节点
                } else {
                    temps[poss[mark]] = item;
                }
            }
        }
        /// <summary>  
        /// Remove the top item from the heap  
        /// </summary>  
        static T Deheap<T>(T[] temps, int len) where T : IComparable<T> {
            var p = 1;
            var temp = temps[p];
            while (2 * p < len) {
                if (2 * p <= len && 2 * p + 1 <= len) {
                    if (temps[2 * p].CompareTo(temps[2 * p + 1]) > 0) {
                        var temp2 = temps[2 * p + 1];
                        if (temps[len].CompareTo(temp2) < 0) {
                            temps[p] = temps[len]; goto step2;
                        } else {
                            temps[p] = temp2;
                        }
                        p = 2 * p + 1;
                    } else {
                        var temp2 = temps[2 * p];
                        if (temps[len].CompareTo(temp2) < 0) {
                            temps[p] = temps[len]; goto step2;
                        } else {
                            temps[p] = temp2;
                        }
                        p *= 2;
                    }
                } else if (2 * p <= len) {
                    var temp2 = temps[2 * p];
                    if (temps[len].CompareTo(temp2) < 0) {
                        temps[p] = temps[len]; goto step2;
                    } else {
                        temps[p] = temp2;
                    }
                    p *= 2;
                }
            }
            temps[p] = temps[len];
        step2:
            return temp;
        }
        //
        public static void SortSelect(this int[] data) {
            var count = data.Length;
            var min = 0; var x = data[0];
            for (int i = 0; i < count - 1; i++) {
                min = i;
                for (int j = i + 1; j < count; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        public static void SortSelectD(this int[] data) {
            var count = data.Length - 1;
            var min = 0; var max = count; var len = (count + 1) / 2;
            for (int i = 0; i < len; i++) {
                min = i; max = count - i;
                if (data[min] > data[max]) {
                    min = min ^ max;
                    max = min ^ max;
                    min = min ^ max;
                }
                for (int j = i + 1; j < count - i; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    } else if (data[j] > data[max]) {
                        max = j;
                    }
                }
                if (min != i) {
                    var temp = data[min];
                    data[min] = data[i];
                    data[i] = temp;
                    if (max == i) max = min;
                }
                if (max != count - i) {
                    var tempmax = data[max];
                    data[max] = data[count - i];
                    data[count - i] = tempmax;
                }
            }
        }
        public static void SortBubble(this int[] data) {
            var len = data.Length;
            for (int j = 0; j < len; j++) {
                for (int i = j; i < len; i++) {
                    if (data[j] > data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        public static void SortInsert(this int[] data) {
            var count = data.Length;
            for (int i = 1; i < count; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }
        }
        //
        public static void SortQuick(this int[] data) {
            QuickSort(data, 0, data.Length - 1);
        }
        private static void QuickSort(int[] numbers, int left, int right) {
            if (left < right) {
                int middle = numbers[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (numbers[++i] < middle) ;
                    while (numbers[--j] > middle) ;
                    if (i >= j) break;
                    Swap(numbers, i, j);
                }
                QuickSort(numbers, left, i - 1);
                QuickSort(numbers, j + 1, right);
            }
        }
        private static void Swap(int[] numbers, int i, int j) {
            int number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        //
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        public static void SortOddEven(this int[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
            }

        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="data"></param>
        public static void SortCocktail(this int[] data) { // the first element of list has index 0
            var bottom = 0;
            var top = data.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom; i < top; i = i + 1) {
                    if (data[i] > data[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(data, i, i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top; i > bottom; i = i - 1) {
                    if (data[i] < data[i - 1]) {
                        Swap(data, i, i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }
        //
        public static void SortSelect(this float[] data) {
            var count = data.Length;
            var min = 0;
            for (int i = 0; i < count - 1; i++) {
                min = i;
                for (int j = i + 1; j < count; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        public static void SortBubble(this float[] data) {
            var len = data.Length;
            for (int j = 0; j < len; j++) {
                for (int i = j; i < len; i++) {
                    if (data[j] > data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        public static void SortInsert(this float[] data) {
            var count = data.Length;
            for (int i = 1; i < count; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }

        }
        //
        public static void SortQuick(this float[] data) {
            QuickSort(data, 0, data.Length - 1);
        }
        private static void QuickSort(float[] data, int left, int right) {
            if (left < right) {
                var middle = data[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (data[++i] < middle) ;
                    while (data[--j] > middle) ;
                    if (i >= j) break;
                    Swap(data, i, j);
                }
                QuickSort(data, left, i - 1);
                QuickSort(data, j + 1, right);
            }
        }
        private static void Swap(float[] numbers, int i, int j) {
            var number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        public static void SortOddEven(this float[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
            }

        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        public static void SortCocktail(this float[] list) { // the first element of list has index 0
            var bottom = 0;
            var top = list.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom; i < top; i = i + 1) {
                    if (list[i] > list[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(list, i, i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top; i > bottom; i = i - 1) {
                    if (list[i] < list[i - 1]) {
                        Swap(list, i, i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }
        public static void SortSelect(this double[] data) {
            var count = data.Length;
            var min = 0;
            for (int i = 0; i < count - 1; i++) {
                min = i;
                for (int j = i + 1; j < count; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        public static void SortBubble(this double[] data) {
            var len = data.Length;
            for (int j = 0; j < len; j++) {
                for (int i = j; i < len; i++) {
                    if (data[j] > data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        public static void SortInsert(this double[] data) {
            var count = data.Length;
            for (int i = 1; i < count; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }

        }
        //
        public static void SortQuick(this double[] data) {
            SortQuick(data, 0, data.Length - 1);
        }
        private static void SortQuick(double[] data, int left, int right) {
            if (left < right) {
                var middle = data[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (data[++i] < middle) ;
                    while (data[--j] > middle) ;
                    if (i >= j) break;
                    Swap(data, i, j);
                }
                SortQuick(data, left, i - 1);
                SortQuick(data, j + 1, right);
            }
        }
        private static void Swap(double[] numbers, int i, int j) {
            var number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        //
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        public static void SortOddEven(this double[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0; i < count - 1; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data, i, i + 1);
                        sorted = false;
                    }
                }
            }
        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        public static void SortCocktail(this double[] list) { // the first element of list has index 0
            var bottom = 0;
            var top = list.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom; i < top; i = i + 1) {
                    if (list[i] > list[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(list, i, i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top; i > bottom; i = i - 1) {
                    if (list[i] < list[i - 1]) {
                        Swap(list, i, i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }
        #endregion
        //
        #region date time
        /// <summary>
        /// 返回一个以星期几为key的 7组 日期集合，一般每组有4天或5天
        /// </summary>
        /// <param name="month"></param>
        /// <returns></returns>
        public static Dictionary<DayOfWeek, List<Tople<bool, DateTime>>> GetCanlenderMonthDays(this DateTime month) {
            var start = month.AddDays(1 - month.Day);
            var current = start;
            var end = month.AddDays(1 - month.Day).AddMonths(1).AddDays(-1);
            var ds = new List<DateTime>();
            while (current < end) {
                ds.Add(current);
                current = current.AddDays(1);
            }
            ds.Add(end);
            var dds = new Dictionary<DayOfWeek, List<Tople<bool, DateTime>>>();
            var weekgroup = from item in ds group item by item.DayOfWeek;
            var wgo = from item in weekgroup orderby item.ElementAt(0).Day select item;
            var markg = wgo.ElementAt(0).Key;
            var wgog = from item in wgo let key = item.Key >= markg group item by key;
            foreach (var item in wgog) {
                if (item.Key) {
                    if (markg == DayOfWeek.Sunday) {
                        foreach (var item2 in item) {
                            var x = (from item3 in item2 select new Tople<bool, DateTime>(true, item3)).ToList();
                            if (item2.Count() == 5) {
                                x.Insert(0, new Tople<bool, DateTime>(false, x[0].Item2.AddDays(-7)));
                            } else {
                                x.Insert(0, new Tople<bool, DateTime>(false, x[0].Item2.AddDays(-7)));
                                x.Add(new Tople<bool, DateTime>(false, x[x.Count - 1].Item2.AddDays(7)));
                            }
                            dds.Add(item2.Key, x);
                        }
                    } else {
                        foreach (var item2 in item) {
                            var x = (from item3 in item2 select new Tople<bool, DateTime>(true, item3)).ToList();
                            if (item2.Count() == 5) {
                                x.Add(new Tople<bool, DateTime>(false, x[x.Count - 1].Item2.AddDays(7)));
                            } else {
                                x.Add(new Tople<bool, DateTime>(false, x[x.Count - 1].Item2.AddDays(7)));
                                x.Add(new Tople<bool, DateTime>(false, x[x.Count - 1].Item2.AddDays(7)));
                            }
                            dds.Add(item2.Key, x);
                        }
                    }
                } else {
                    foreach (var item2 in item) {
                        var x = (from item3 in item2 select new Tople<bool, DateTime>(true, item3)).ToList();
                        if (item2.Count() == 5) {
                            x.Insert(0, new Tople<bool, DateTime>(false, x[0].Item2.AddDays(-7)));
                        } else {
                            x.Insert(0, new Tople<bool, DateTime>(false, x[0].Item2.AddDays(-7)));
                            x.Add(new Tople<bool, DateTime>(false, x[x.Count - 1].Item2.AddDays(7)));
                        }
                        dds.Add(item2.Key, x);
                    }
                }
            }
            return dds;
        }
        #endregion
        //
        #region string
        /// <summary>
        /// 计算相同长度两个字符串中是否包含相同的char集组合,要求char集不重复
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <returns></returns>
        public static bool CheckMatch(this string s1, string s2) {
            if ((string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) || (s1.Length != s2.Length)) return false;
            int[] check = new int[128];
            var len = s1.Length;
            foreach (var c in s1) {
                check[c]++;
            }
            foreach (var c in s2) {
                check[c]--;
            }
            return check.Max() == 0 && check.Min() == 0;
        }
        /// <summary>
        /// 求一个字符串的回溯函数。
        /// 约定序列下标从0开始。
        /// 回溯函数是整数集[0,n-1]到N的映射，n为字符串的长度。
        /// 回溯函数的定义：
        /// 设存在非空序列L，i为其合法下标；
        /// L[i]的前置序列集为：{空集,L中所有以i-1为最后一个元素下标的子序列}
        /// L的前置序列集为：{空集,L中所有以0为第一个元素下标的子序列}
        /// 下标i的回溯函数值的定义为：
        /// 如果i=0,回溯函数值为-1
        /// 否则i的回溯函数值为i的前置序列集和L的前置序列集中相等元素的最大长度,但是相等的两个元素不能是L中的同一个子串，例如[0-i,1]~[i-1,0]reversed
        /// 换句话说是，设集合V={x,x属于i的前置序列集,并且x属于L的前置序列集，并且x的长度小于i}，回溯函数值为max(V).length
        /// 当i=0时并不存在这样的一个x，所以约定此时的回溯函数值为-1
        /// 回溯函数的意义：
        /// 如果子串中标号为j的字符同主串失配，那么将子串回溯到next[j]继续与主串匹配，如果next[j]=-1,则主串的匹配点后移一位，同子串的第一个元素开始匹配。
        /// 同一般的模式匹配算法相比，kmp通过回溯函数在失配的情况下跳过了若干轮匹配(向右滑动距离可能大于1)
        /// kmp算法保证跳过去的这些轮匹配一定是失配的，这一点可以证明
        /// </summary>
        /// <param name="pattern">模式串，上面的注释里将其称为子串</param>
        /// <returns>回溯函数是kmp算法的核心，本函数依照其定义求出回溯函数，KMP函数依照其意义使用回溯函数。</returns>
        static int[] Next(string pattern) {
            int[] next = new int[pattern.Length];
            next[0] = -1;
            if (pattern.Length < 2) //如果只有1个元素不用kmp效率会好一些
            {
                return next;
            }
            next[1] = 0;    //第二个元素的回溯函数值必然是0，可以证明：
            //1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
            int i = 2;  //正被计算next值的字符的索引
            int j = 0;  //计算next值所需要的中间变量，每一轮迭代初始时j总为next[i-1]
            while (i < pattern.Length)    //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
            { //状态点
                if (pattern[i - 1] == pattern[j])   //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
                {   //如果L[i-1]等于L[j]，那么next[i] = j + 1
                    next[i++] = ++j;
                } else {   //如果不相等则检查next[i]的下一个可能值----next[j]
                    j = next[j];
                    if (j == -1)    //如果j == -1则表示next[i]的值是1
                    {   //可以把这一部分提取出来与外层判断合并
                        //书上的kmp代码很难理解的一个原因就是已经被优化，从而遮蔽了其实际逻辑
                        next[i++] = ++j;
                    }
                }
            }
            return next;
        }
        /// <summary>
        /// KMP函数同普通的模式匹配函数的差别在于使用了next函数来使模式串一次向右滑动多位称为可能
        /// next函数的本质是提取重复的计算
        /// </summary>
        /// <param name="source">主串</param>
        /// <param name="pattern">用于查找主串中一个位置的模式串</param>
        /// <returns>-1表示没有匹配，否则返回匹配的标号</returns>
        public static int ExecuteKMP(this string source, string pattern) {
            int[] next = Next(pattern);
            int i = 0;  //主串指针
            int j = 0;  //模式串指针
            //如果子串没有匹配完毕并且主串没有搜索完成
            while (j < pattern.Length && i < source.Length) {
                if (source[i] == pattern[j])    //i和j的逻辑意义体现于此，用于指示本轮迭代中要判断是否相等的主串字符和模式串字符
                {
                    i++;
                    j++;
                } else {
                    j = next[j];    //依照指示迭代回溯
                    if (j == -1)    //回溯有情况，这是第二种
                    {
                        i++;
                        j++;
                    }
                }
            }
            //如果j==pattern.Length则表示循环的退出是由于子串已经匹配完毕而不是主串用尽
            return j < pattern.Length ? -1 : i - j;
        }
        //
        public static int Kmp(char[] a, char[] b, int pos) {
            int i = pos, j = 0;
            int lena = a.Length, lenb = b.Length;
            var count = 0;
            while ((i <= lena - 1) && (j <= lenb - 1)) {
                if (a[i] == b[j]) { ++i; ++j; } else { i = i - j + 1; j = 0; }
                count++;
            }
            if (j > lenb - 1)
                return i - lenb;
            else
                return 0;
        }
        /// <summary>
        /// Compute the distance between two strings.(edit distance)
        /// </summary>
        public static int Levenshtein(this string s, string t) {
            int n = s.Length;
            int m = t.Length;
            int[,] d = new int[n + 1, m + 1];
            // Step 1
            if (n == 0) {
                return m;
            }
            if (m == 0) {
                return n;
            }
            // Step 2
            for (int i = 0; i <= n; d[i, 0] = i++) {
            }
            for (int j = 0; j <= m; d[0, j] = j++) {
            }
            // Step 3
            for (int i = 1; i <= n; i++) {
                //Step 4
                for (int j = 1; j <= m; j++) {
                    // Step 5
                    int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                    // Step 6
                    d[i, j] = Math.Min(
                        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                        d[i - 1, j - 1] + cost);
                }
            }
            // Step 7
            return d[n, m];
        }
        public static string Subtract(this string a, string b) {
            if (a.Length > b.Length) {
                var len = a.Length - b.Length;
                if (a.Substring(len) == b) {
                    return a.Remove(len, b.Length);
                }
            }
            throw new Exception("the two string must match");
        }
        /// <summary>
        /// 根据string 源返回 特定的 结构组
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="source"></param>
        /// <param name="patterns"></param>
        /// <returns></returns>
        public static T[] ToTypeValues<T>(this string source, params char[] patterns) where T : struct {
            var ss = source.Split(patterns, StringSplitOptions.RemoveEmptyEntries);
            var ts = new List<T>();
            switch (typeof(T).Name) {
                case "Int32": foreach (var item in ss) { ts.Add((T)(object)Convert.ToInt32(item)); } break;
                case "Int64": foreach (var item in ss) { ts.Add((T)(object)Convert.ToInt64(item)); } break;
                case "Int16": foreach (var item in ss) { ts.Add((T)(object)Convert.ToInt16(item)); } break;
                case "Byte": foreach (var item in ss) { ts.Add((T)(object)Convert.ToByte(item)); } break;
                case "Double": foreach (var item in ss) { ts.Add((T)(object)Convert.ToDouble(item)); } break;
                case "Single": foreach (var item in ss) { ts.Add((T)(object)Convert.ToSingle(item)); } break;
                case "Boolean": foreach (var item in ss) { ts.Add((T)(object)Convert.ToBoolean(item)); } break;
                case "DateTime": foreach (var item in ss) { ts.Add((T)(object)Convert.ToDateTime(item)); } break;
            }
            return ts.ToArray();
        }
        public static string MaxSubstr(this string s1, string s2) {
            if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2)) return null; else if (s1 == s2) return s1;
            int max = 0; int end = 0; int[,] a = new int[s1.Length, s2.Length];
            for (int i = 0; i < s1.Length; i++) {
                for (int j = 0; j < s2.Length; j++) {
                    int n = (i - 1 >= 0 && j - 1 >= 0) ? a[i - 1, j - 1] : 0;
                    a[i, j] = s1[i] == s2[j] ? 1 + n : 0;
                    if (a[i, j] > max) { max = a[i, j]; end = i; }
                }
            }
            return s1.Substring(end - max + 1, max);
        }
        #endregion
        //
        #region double[,]
        public static bool Equal(this double[,] owner, double[,] target) {
            var r = false;
            var len0 = owner.GetLength(0); var len1 = owner.GetLength(1);
            if (owner.Length == target.Length && len0 == target.GetLength(0) && len1 == target.GetLength(1)) {
                return false;
            }
            for (int i = 0; i < len0; i++) {
                for (int j = 0; j < len1; j++) {
                    if (owner[i, j] != target[i, j]) {
                        r = false; break;
                    }
                }
            }
            return r;
        }
        /// <summary>
        /// 矩阵乘
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        public static double[,] Mul(this double[,] left, double[,] right) {
            //判断行列是否匹配
            var len1 = left.GetLength(0); var len2 = right.GetLength(1);
            var len3 = left.GetLength(1); var len4 = right.GetLength(0);
            if (len3 != len4)
                throw new Exception("乘法条件不匹配，请确保前行后列长度相等");
            var x1 = new double[len1, len1];
            for (int k = 0; k < len2; k++) {
                for (int i = 0; i < len1; i++) {
                    for (int j = 0; j < len4; j++) {
                        x1[i, k] += left[i, j] * right[j, k];
                    }
                }
            }
            return x1;
        }
        //
        /// <summary>
        /// 矩阵的逆
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        public static double[,] Inverse(this double[,] target) {
            if (target.GetLength(0) != target.GetLength(1)) {
                throw new Exception("只有方阵才有逆");
            }
            var level = target.GetLength(0);
            double dMatrixValue = MatrixValue(target, level);
            if (dMatrixValue == 0) return null;
            double[,] dReverseMatrix = new double[level, 2 * level];
            double x, c;
            // Init Reverse matrix
            for (int i = 0; i < level; i++) {
                for (int j = 0; j < 2 * level; j++) {
                    if (j < level)
                        dReverseMatrix[i, j] = target[i, j];
                    else
                        dReverseMatrix[i, j] = 0;
                }
                dReverseMatrix[i, level + i] = 1;
            }
            for (int i = 0, j = 0; i < level && j < level; i++, j++) {
                if (dReverseMatrix[i, j] == 0) {
                    int m = i;
                    for (; target[m, j] == 0; m++) ;
                    if (m == level)
                        return null;
                    else {
                        // Add i-row with m-row
                        for (int n = j; n < 2 * level; n++)
                            dReverseMatrix[i, n] += dReverseMatrix[m, n];
                    }
                }
                // Format the i-row with "1" start
                x = dReverseMatrix[i, j];
                if (x != 1) {
                    for (int n = j; n < 2 * level; n++)
                        if (dReverseMatrix[i, n] != 0)
                            dReverseMatrix[i, n] /= x;
                }
                // Set 0 to the current column in the rows after current row
                for (int s = level - 1; s > i; s--) {
                    x = dReverseMatrix[s, j];
                    for (int t = j; t < 2 * level; t++)
                        dReverseMatrix[s, t] -= (dReverseMatrix[i, t] * x);
                }
            }
            // Format the first matrix into unit-matrix
            for (int i = level - 2; i >= 0; i--) {
                for (int j = i + 1; j < level; j++)
                    if (dReverseMatrix[i, j] != 0) {
                        c = dReverseMatrix[i, j];
                        for (int n = j; n < 2 * level; n++)
                            dReverseMatrix[i, n] -= (c * dReverseMatrix[j, n]);
                    }
            }
            double[,] dReturn = new double[level, level];
            for (int i = 0; i < level; i++)
                for (int j = 0; j < level; j++)
                    dReturn[i, j] = dReverseMatrix[i, j + level];
            return dReturn;
        }
        static double MatrixValue(double[,] matrixList, int level) {
            double[,] dMatrix = new double[level, level];
            for (int i = 0; i < level; i++)
                for (int j = 0; j < level; j++)
                    dMatrix[i, j] = matrixList[i, j];
            double c, x;
            int k = 1;
            for (int i = 0, j = 0; i < level && j < level; i++, j++) {
                if (dMatrix[i, j] == 0) {
                    int m = i;
                    for (; dMatrix[m, j] == 0; m++) ;
                    if (m == level)
                        return 0;
                    else {
                        // Row change between i-row and m-row
                        for (int n = j; n < level; n++) {
                            c = dMatrix[i, n];
                            dMatrix[i, n] = dMatrix[m, n];
                            dMatrix[m, n] = c;
                        }
                        // Change value pre-value
                        k *= (-1);
                    }
                }
                // Set 0 to the current column in the rows after current row
                for (int s = level - 1; s > i; s--) {
                    x = dMatrix[s, j];
                    for (int t = j; t < level; t++)
                        dMatrix[s, t] -= dMatrix[i, t] * (x / dMatrix[i, j]);
                }
            }
            double sn = 1;
            for (int i = 0; i < level; i++) {
                if (dMatrix[i, i] != 0)
                    sn *= dMatrix[i, i];
                else
                    return 0;
            }
            return k * sn;
        }
        /// <summary>
        /// 使用Gauss 消解法求方阵的det值
        /// </summary>
        /// <returns></returns>
        public static double Det(this double[,] m) {
            int i, j, k, nis = 0, js = 0, l, u, v;
            double f, det, q, d;
            // 初值
            f = 1.0;
            det = 1.0;
            // 消元
            var cols = m.GetLength(1);
            var rows = m.GetLength(0);
            if (cols != rows) throw new Exception("nor square,cols and rows must be equal.");
            var ele = new List<double>();
            for (int ii = 0; ii < rows; ii++) {
                for (int jj = 0; jj < cols; jj++) {
                    ele.Add(m[ii, jj]);
                }
            }
            var elements = new double[m.Length];
            ele.CopyTo(elements);
            ele = null;
            for (k = 0; k <= cols - 2; k++) {
                q = 0.0;
                for (i = k; i <= cols - 1; i++) {
                    for (j = k; j <= cols - 1; j++) {
                        l = i * cols + j;
                        d = Math.Abs(elements[l]);
                        if (d > q) {
                            q = d;
                            nis = i;
                            js = j;
                        }
                    }
                }
                if (q == 0.0) {
                    det = 0.0;
                    return (det);
                }
                if (nis != k) {
                    f = -f;
                    for (j = k; j <= cols - 1; j++) {
                        u = k * cols + j;
                        v = nis * cols + j;
                        d = elements[u];
                        elements[u] = elements[v];
                        elements[v] = d;
                    }
                }
                if (js != k) {
                    f = -f;
                    for (i = k; i <= cols - 1; i++) {
                        u = i * cols + js;
                        v = i * cols + k;
                        d = elements[u];
                        elements[u] = elements[v];
                        elements[v] = d;
                    }
                }
                l = k * cols + k;
                det = det * elements[l];
                for (i = k + 1; i <= cols - 1; i++) {
                    d = elements[i * cols + k] / elements[l];
                    for (j = k + 1; j <= cols - 1; j++) {
                        u = i * cols + j;
                        elements[u] = elements[u] - d * elements[k * cols + j];
                    }
                }
            }
            // 求值
            det = f * det * elements[cols * cols - 1];
            return det;
        }
        #endregion
        //
        #region INotifPc
        public static void UpdateAll(this INotifyPc inpc) {
            var t = inpc.GetType();
            var it = from p in t.GetProperties()
                     select p;
            foreach (var p in it) {
                inpc.OnPropertyChanged(p.Name);
            }
        }
        public static void UpdateAllSubs(this INotifyPc inpc) {
            var t = inpc.GetType();
            var it = from p in t.GetProperties()
                     where p.PropertyType is INotifyPc
                     select p;
            foreach (var p in it) {
                inpc.OnPropertyChanged(p.Name);
            }
        }
        public static void Update(this INotifyPc inpc, params string[] ns) {
            var t = inpc.GetType();
            var x = from item in t.GetProperties()
                    join item2 in ns
                        on item.Name equals item2
                    select item;
            foreach (var item in x) {
                inpc.OnPropertyChanged(item.Name);
            }
        }
        public static void UpdateCall(this INotifyPc inpc, params string[] ns) {
            var t = inpc.GetType();
            var x = from item in t.GetProperties()
                    join item2 in ns
                        on item.Name equals item2
                    select item;
            foreach (var item in x) {
                inpc.OnPropertyChanged(item.Name);
            }
            inpc.Act.Execute(inpc.ActParam);
        }
        public static void Call(this INotifyPc inpc, object p = null) {
            if (inpc.Act != null)
                inpc.Act.Execute(inpc.ActParam ?? p);
        }
        //
        public static object CloneBase(this INotifyPc npc) {
            var t = Activator.CreateInstance(npc.GetType().BaseType);
            var tt = npc.GetType().BaseType;
            var it = from p in tt.GetProperties()
                     select p;
            foreach (var p in it) {
                p.SetValue(t, p.GetValue(npc, null), null);
            }
            return t;
        }
        public static T CloneBase<T>(this INotifyPc npc) where T : class {
            return (T)npc.CloneBase();
        }
        #endregion
        //
        #region IEqualityComparer<T>
        public static IEqualityComparer<T> CreateComparer<T, Key>(Func<T, Key> keySelector) {
            return new CommonEqualityComparer<T, Key>(keySelector);
        }
        public static IEqualityComparer<T> CreateComparer<T, Key>(Func<T, Key> keySelector, IEqualityComparer<Key> comparer) {
            return new CommonEqualityComparer<T, Key>(keySelector, comparer);
        }
        #endregion
        //
        #region serializer
        //json
        public static T JsonDeserialise<T>(this string json) {
            T obj = default(T);
            using (var ms = new MemoryStream(Encoding.Unicode.GetBytes(json))) {
                var serializer = new DataContractJsonSerializer(typeof(T));
                obj = (T)serializer.ReadObject(ms);
                return obj;
            }
        }
        public static string JsonSerialize<T>(this T obj) {
            var serializer = new DataContractJsonSerializer(obj.GetType());
            using (var ms = new MemoryStream()) {
                serializer.WriteObject(ms, obj);
                var json = ms.ToArray();
                return Encoding.UTF8.GetString(json, 0, json.Length);
            }
        }
        //xml
        public static T XmlDeserialize<T>(this XNode xn) {
            T t = default(T);
            var xs = new System.Xml.Serialization.XmlSerializer(typeof(T));
            t = (T)xs.Deserialize(xn.CreateReader());
            return t;
        }
        public static string XmlSerialize<T>(this T t) {
            var xdoc = new StringBuilder();
            var xw = XmlWriter.Create(xdoc, new XmlWriterSettings { Encoding = Encoding.UTF8, Indent = true, IndentChars = "    ", NewLineChars = "\n" });
            xw.WriteProcessingInstruction("xml", "version='1.0' encoding='UTF-8'");
            var xsn = new XmlSerializerNamespaces();
            xsn.Add("", "");
            var serialize = new System.Xml.Serialization.XmlSerializer(typeof(T));
            serialize.Serialize(xw, t, xsn);
            return xdoc.ToString();
        }
        //byte[]
        public static T BytesDeserialize<T>(this byte[] bs) {
            var dsc = new System.Runtime.Serialization.DataContractSerializer(typeof(T));
            var mem = new MemoryStream(bs);
            return (T)dsc.ReadObject(mem);
        }
        public static byte[] BytesSerialize<T>(this T obj) {
            var ms = new MemoryStream();
            var ser = new DataContractSerializer(typeof(T));
            ser.WriteObject(ms, obj);
            return ms.ToArray();
        }
        #endregion
        //
        #region xml contract serializer
        public static T XmlContractDeserialize<T>(this XNode xn) {
            T t = default(T);
            var xs = new System.Runtime.Serialization.DataContractSerializer(typeof(T));
            var xr = XmlDictionaryReader.CreateDictionaryReader(xn.CreateReader());
            t = (T)xs.ReadObject(xr);
            return t;
        }
        public static string XmlContractSerialize<T>(this T t) {
            var xdoc = new StringBuilder();
            var xw = XmlWriter.Create(xdoc, new XmlWriterSettings { Encoding = Encoding.UTF8, Indent = true, IndentChars = "    ", NewLineChars = "\n" });
            xw.WriteProcessingInstruction("xml", "version='1.0' encoding='UTF-8'");
            var xdw = XmlDictionaryWriter.CreateDictionaryWriter(xw);
            var ser = new System.Runtime.Serialization.DataContractSerializer(typeof(T));
            ser.WriteObject(xdw, t);
            xw.Dispose();
            return xdoc.ToString();
        }
        #endregion
        //
        #region collection
        public static HashSet<T> Intersect<T>(this HashSet<T> a, HashSet<T> b) {
            T[] temp = new T[a.Count];
            a.CopyTo(temp);
            var r = new HashSet<T>(temp);
            r.IntersectWith(b);
            return r;
        }
        public static HashSet<T> Except<T>(this HashSet<T> a, HashSet<T> b) {
            T[] temp = new T[a.Count];
            a.CopyTo(temp);
            var r = new HashSet<T>(temp);
            r.ExceptWith(b);
            return r;
        }
        public static HashSet<T> SymmetricExcept<T>(this HashSet<T> a, HashSet<T> b) {
            T[] temp = new T[a.Count];
            a.CopyTo(temp);
            var r = new HashSet<T>(temp);
            r.SymmetricExceptWith(b);
            return r;
        }
        public static HashSet<T> Union<T>(this HashSet<T> a, HashSet<T> b) {
            T[] temp = new T[a.Count];
            a.CopyTo(temp);
            var r = new HashSet<T>(temp);
            r.UnionWith(b);
            return r;
        }
        #endregion
        //
        #region wcf
        static Action<object> eWcfRpcCallback;
        static Dictionary<string, Action<object>> eWcfRpcCallbacks = new Dictionary<string, Action<object>>();
        static Action<Exception> eWcfRpcErrorCallback;
        /// <summary>
        /// 务必在最后一个调用之后加 are.WaitOne();以等于
        /// 最后一次调用 的异步回调释放 are.Set();
        /// </summary>
        public static AutoResetEvent are = new AutoResetEvent(true);
        public static void ServiceImplement(Action<Tople<string>> wcfcall, Action<object> callback, bool isOrder = false, Action<Exception> error = null) {
            if (!isOrder) {
                Task.Factory.StartNew(() => {
                    eWcfRpcErrorCallback = error;
                    var methodName = Tople.C<string>(string.Empty);
                    wcfcall.Invoke(methodName);
                    if (!eWcfRpcCallbacks.ContainsKey(methodName.Item1))
                        eWcfRpcCallbacks.Add(methodName.Item1, callback);
                });
            } else {
                Task.Factory.StartNew(pare => {
                    var parelocal = pare as AutoResetEvent;
                    if (parelocal.WaitOne()) {
                        //Interlocked.Exchange(ref mark, 0);
                        callback += x => {
                            eWcfRpcCallback = null;
                            parelocal.Set();
                        };
                        eWcfRpcCallback = callback;
                        error += e => {
                            parelocal.Set();
                        };
                        eWcfRpcErrorCallback = error;
                        wcfcall.Invoke(new Tople<string>(string.Empty));
                    }
                }, are);
            }
        }
        static SynchronizationContext synchronizationContext = SynchronizationContext.Current;
        public static void WcfRpcCallback(object result, string methodName) {
            synchronizationContext.Post(sopc => {
                //Action<object> act = eWcfRpcCallbacks[methodName]??eWcfRpcCallback;                    
                Action<object> act = null;
                if (eWcfRpcCallbacks.ContainsKey(methodName)) {
                    act = eWcfRpcCallback = eWcfRpcCallbacks[methodName];
                    eWcfRpcCallbacks.Remove(methodName);
                } else {
                    act = eWcfRpcCallback;
                }
                act.Invoke(result);
            }, null);
        }
        public static void WcfRpcError(Exception e) {
            synchronizationContext.Post(sopc => {
                eWcfRpcErrorCallback.Invoke(e);
            }, null);
        }
        #endregion
        //
        #region color
        /// <summary>
        /// 把4个0-255的值 转成一个int代表颜色
        /// 从左到右按：
        /// A,R,G,B的顺序 按位组合而成,若要取出其中的byte[]那么请使用
        /// BitConverter.GetBytes(...) 方法
        /// </summary>
        /// <param name="a">alpha channel</param>
        /// <param name="r">red</param>
        /// <param name="g">green</param>
        /// <param name="b">blue</param>
        /// <returns></returns>
        public static uint GetColor(byte a, byte r, byte g, byte b) {
            uint color = 0;
            var bytelen = 8;
            color += (uint)a << bytelen * 0;
            color += (uint)r << bytelen * 1;
            color += (uint)g << bytelen * 2;
            color += (uint)b << bytelen * 3;
            return color;
        }
        public static byte[] GetArgb(uint value) {
            //return BitConverter.GetBytes(value).Reverse().ToArray();
            var x = new byte[4];
            var bytelen = 8;
            x[0] = (byte)(value >> bytelen * 0);
            x[1] = (byte)(value >> bytelen * 1);
            x[2] = (byte)(value >> bytelen * 2);
            x[3] = (byte)(value >> bytelen * 3);
            return x;
        }
        #endregion
        //
        #region search
        public static int BinSearch(this int[] arr, int key) {
            int left, right;
            int mid;
            left = 0;
            right = arr.Length;
            while (left <= right) {
                mid = (left + right) / 2;
                if (key < arr[mid]) {
                    right = mid - 1;
                } else if (key > arr[mid]) {
                    left = mid + 1;
                } else
                    return mid;
            }
            return -1;
        }
        public static int BinSearch(this float[] arr, int key) {
            int left, right;
            int mid;
            left = 0;
            right = arr.Length;
            while (left <= right) {
                mid = (left + right) / 2;
                if (key < arr[mid]) {
                    right = mid - 1;
                } else if (key > arr[mid]) {
                    left = mid + 1;
                } else
                    return mid;
            }
            return -1;
        }
        public static int BinSearch(this double[] arr, int key) {
            int left, right;
            int mid;
            left = 0;
            right = arr.Length;
            while (left <= right) {
                mid = (left + right) / 2;
                if (key < arr[mid]) {
                    right = mid - 1;
                } else if (key > arr[mid]) {
                    left = mid + 1;
                } else
                    return mid;
            }
            return -1;
        }
        #endregion
        //
        #region md5
        //from microsoft @copyright
        //Prevent CSC from adding a default public constructor
        public static byte[] GetHash(this string input, Encoding encoding) {
            if (null == input)
                throw new System.ArgumentNullException("input", "Unable to calculate hash over null input data");
            if (null == encoding)
                throw new System.ArgumentNullException("encoding", "Unable to calculate hash over a string without a default encoding. Consider using the GetHash(string) overload to use UTF8 Encoding");
            byte[] target = encoding.GetBytes(input);
            return GetHash(target);
        }

        public static byte[] GetHash(this string input) {
            return GetHash(input, new UTF8Encoding());
        }

        public static string GetHashString(this byte[] input) {
            if (null == input)
                throw new System.ArgumentNullException("input", "Unable to calculate hash over null input data");
            string retval = BitConverter.ToString(GetHash(input));
            retval = retval.Replace("-", "");
            return retval;
        }

        public static string GetHashString(this string input, Encoding encoding) {
            if (null == input)
                throw new System.ArgumentNullException("input", "Unable to calculate hash over null input data");
            if (null == encoding)
                throw new System.ArgumentNullException("encoding", "Unable to calculate hash over a string without a default encoding. Consider using the GetHashString(string) overload to use UTF8 Encoding");
            byte[] target = encoding.GetBytes(input);
            return GetHashString(target);
        }

        public static string GetHashString(this string input) {
            return GetHashString(input, new UTF8Encoding());
        }

        public static byte[] GetHash(this byte[] input) {
            if (null == input)
                throw new System.ArgumentNullException("input", "Unable to calculate hash over null input data");
            //Intitial values defined in RFC 1321
            ABCDStruct abcd = new ABCDStruct();
            abcd.A = 0x67452301;
            abcd.B = 0xefcdab89;
            abcd.C = 0x98badcfe;
            abcd.D = 0x10325476;
            //We pass in the input array by block, the final block of data must be handled specialy for padding & length embeding
            int startIndex = 0;
            while (startIndex <= input.Length - 64) {
                GetHashBlock(input, ref abcd, startIndex);
                startIndex += 64;
            }
            // The final data block. 
            return GetHashFinalBlock(input, startIndex, input.Length - startIndex, abcd, (Int64)input.Length * 8);
        }

        internal static byte[] GetHashFinalBlock(byte[] input, int ibStart, int cbSize, ABCDStruct ABCD, Int64 len) {
            byte[] working = new byte[64];
            byte[] length = BitConverter.GetBytes(len);
            //Padding is a single bit 1, followed by the number of 0s required to make size congruent to 448 modulo 512. Step 1 of RFC 1321  
            //The CLR ensures that our buffer is 0-assigned, we don't need to explicitly set it. This is why it ends up being quicker to just
            //use a temporary array rather then doing in-place assignment (5% for small inputs)
            Array.Copy(input, ibStart, working, 0, cbSize);
            working[cbSize] = 0x80;
            //We have enough room to store the length in this chunk
            if (cbSize < 56) {
                Array.Copy(length, 0, working, 56, 8);
                GetHashBlock(working, ref ABCD, 0);
            } else {//We need an aditional chunk to store the length
                GetHashBlock(working, ref ABCD, 0);
                //Create an entirely new chunk due to the 0-assigned trick mentioned above, to avoid an extra function call clearing the array
                working = new byte[64];
                Array.Copy(length, 0, working, 56, 8);
                GetHashBlock(working, ref ABCD, 0);
            }
            byte[] output = new byte[16];
            Array.Copy(BitConverter.GetBytes(ABCD.A), 0, output, 0, 4);
            Array.Copy(BitConverter.GetBytes(ABCD.B), 0, output, 4, 4);
            Array.Copy(BitConverter.GetBytes(ABCD.C), 0, output, 8, 4);
            Array.Copy(BitConverter.GetBytes(ABCD.D), 0, output, 12, 4);
            return output;
        }
        // Performs a single block transform of MD5 for a given set of ABCD inputs
        /* If implementing your own hashing framework, be sure to set the initial ABCD correctly according to RFC 1321:
        //    A = 0x67452301;
        //    B = 0xefcdab89;
        //    C = 0x98badcfe;
        //    D = 0x10325476;
        */
        internal static void GetHashBlock(byte[] input, ref ABCDStruct ABCDValue, int ibStart) {
            uint[] temp = Converter(input, ibStart);
            uint a = ABCDValue.A;
            uint b = ABCDValue.B;
            uint c = ABCDValue.C;
            uint d = ABCDValue.D;
            //
            a = r1(a, b, c, d, temp[0], 7, 0xd76aa478);
            d = r1(d, a, b, c, temp[1], 12, 0xe8c7b756);
            c = r1(c, d, a, b, temp[2], 17, 0x242070db);
            b = r1(b, c, d, a, temp[3], 22, 0xc1bdceee);
            a = r1(a, b, c, d, temp[4], 7, 0xf57c0faf);
            d = r1(d, a, b, c, temp[5], 12, 0x4787c62a);
            c = r1(c, d, a, b, temp[6], 17, 0xa8304613);
            b = r1(b, c, d, a, temp[7], 22, 0xfd469501);
            a = r1(a, b, c, d, temp[8], 7, 0x698098d8);
            d = r1(d, a, b, c, temp[9], 12, 0x8b44f7af);
            c = r1(c, d, a, b, temp[10], 17, 0xffff5bb1);
            b = r1(b, c, d, a, temp[11], 22, 0x895cd7be);
            a = r1(a, b, c, d, temp[12], 7, 0x6b901122);
            d = r1(d, a, b, c, temp[13], 12, 0xfd987193);
            c = r1(c, d, a, b, temp[14], 17, 0xa679438e);
            b = r1(b, c, d, a, temp[15], 22, 0x49b40821);
            //
            a = r2(a, b, c, d, temp[1], 5, 0xf61e2562);
            d = r2(d, a, b, c, temp[6], 9, 0xc040b340);
            c = r2(c, d, a, b, temp[11], 14, 0x265e5a51);
            b = r2(b, c, d, a, temp[0], 20, 0xe9b6c7aa);
            a = r2(a, b, c, d, temp[5], 5, 0xd62f105d);
            d = r2(d, a, b, c, temp[10], 9, 0x02441453);
            c = r2(c, d, a, b, temp[15], 14, 0xd8a1e681);
            b = r2(b, c, d, a, temp[4], 20, 0xe7d3fbc8);
            a = r2(a, b, c, d, temp[9], 5, 0x21e1cde6);
            d = r2(d, a, b, c, temp[14], 9, 0xc33707d6);
            c = r2(c, d, a, b, temp[3], 14, 0xf4d50d87);
            b = r2(b, c, d, a, temp[8], 20, 0x455a14ed);
            a = r2(a, b, c, d, temp[13], 5, 0xa9e3e905);
            d = r2(d, a, b, c, temp[2], 9, 0xfcefa3f8);
            c = r2(c, d, a, b, temp[7], 14, 0x676f02d9);
            b = r2(b, c, d, a, temp[12], 20, 0x8d2a4c8a);
            //
            a = r3(a, b, c, d, temp[5], 4, 0xfffa3942);
            d = r3(d, a, b, c, temp[8], 11, 0x8771f681);
            c = r3(c, d, a, b, temp[11], 16, 0x6d9d6122);
            b = r3(b, c, d, a, temp[14], 23, 0xfde5380c);
            a = r3(a, b, c, d, temp[1], 4, 0xa4beea44);
            d = r3(d, a, b, c, temp[4], 11, 0x4bdecfa9);
            c = r3(c, d, a, b, temp[7], 16, 0xf6bb4b60);
            b = r3(b, c, d, a, temp[10], 23, 0xbebfbc70);
            a = r3(a, b, c, d, temp[13], 4, 0x289b7ec6);
            d = r3(d, a, b, c, temp[0], 11, 0xeaa127fa);
            c = r3(c, d, a, b, temp[3], 16, 0xd4ef3085);
            b = r3(b, c, d, a, temp[6], 23, 0x04881d05);
            a = r3(a, b, c, d, temp[9], 4, 0xd9d4d039);
            d = r3(d, a, b, c, temp[12], 11, 0xe6db99e5);
            c = r3(c, d, a, b, temp[15], 16, 0x1fa27cf8);
            b = r3(b, c, d, a, temp[2], 23, 0xc4ac5665);
            //
            a = r4(a, b, c, d, temp[0], 6, 0xf4292244);
            d = r4(d, a, b, c, temp[7], 10, 0x432aff97);
            c = r4(c, d, a, b, temp[14], 15, 0xab9423a7);
            b = r4(b, c, d, a, temp[5], 21, 0xfc93a039);
            a = r4(a, b, c, d, temp[12], 6, 0x655b59c3);
            d = r4(d, a, b, c, temp[3], 10, 0x8f0ccc92);
            c = r4(c, d, a, b, temp[10], 15, 0xffeff47d);
            b = r4(b, c, d, a, temp[1], 21, 0x85845dd1);
            a = r4(a, b, c, d, temp[8], 6, 0x6fa87e4f);
            d = r4(d, a, b, c, temp[15], 10, 0xfe2ce6e0);
            c = r4(c, d, a, b, temp[6], 15, 0xa3014314);
            b = r4(b, c, d, a, temp[13], 21, 0x4e0811a1);
            a = r4(a, b, c, d, temp[4], 6, 0xf7537e82);
            d = r4(d, a, b, c, temp[11], 10, 0xbd3af235);
            c = r4(c, d, a, b, temp[2], 15, 0x2ad7d2bb);
            b = r4(b, c, d, a, temp[9], 21, 0xeb86d391);
            //
            ABCDValue.A = unchecked(a + ABCDValue.A);
            ABCDValue.B = unchecked(b + ABCDValue.B);
            ABCDValue.C = unchecked(c + ABCDValue.C);
            ABCDValue.D = unchecked(d + ABCDValue.D);
            return;
        }
        //Manually unrolling these equations nets us a 20% performance improvement
        private static uint r1(uint a, uint b, uint c, uint d, uint x, int s, uint t) {
            //                  (b + LSR((a + F(b, c, d) + x + t), s))
            //F(x, y, z)        ((x & y) | ((x ^ 0xFFFFFFFF) & z))
            return unchecked(b + LSR((a + ((b & c) | ((b ^ 0xFFFFFFFF) & d)) + x + t), s));
        }

        private static uint r2(uint a, uint b, uint c, uint d, uint x, int s, uint t) {
            //                  (b + LSR((a + G(b, c, d) + x + t), s))
            //G(x, y, z)        ((x & z) | (y & (z ^ 0xFFFFFFFF)))
            return unchecked(b + LSR((a + ((b & d) | (c & (d ^ 0xFFFFFFFF))) + x + t), s));
        }

        private static uint r3(uint a, uint b, uint c, uint d, uint x, int s, uint t) {
            //                  (b + LSR((a + H(b, c, d) + k + i), s))
            //H(x, y, z)        (x ^ y ^ z)
            return unchecked(b + LSR((a + (b ^ c ^ d) + x + t), s));
        }

        private static uint r4(uint a, uint b, uint c, uint d, uint x, int s, uint t) {
            //                  (b + LSR((a + I(b, c, d) + k + i), s))
            //I(x, y, z)        (y ^ (x | (z ^ 0xFFFFFFFF)))
            return unchecked(b + LSR((a + (c ^ (b | (d ^ 0xFFFFFFFF))) + x + t), s));
        }
        // Implementation of left rotate
        // s is an int instead of a uint becuase the CLR requires the argument passed to >>/<< is of 
        // type int. Doing the demoting inside this function would add overhead.
        private static uint LSR(uint i, int s) {
            return ((i << s) | (i >> (32 - s)));
        }
        //Convert input array into array of UInts
        private static uint[] Converter(byte[] input, int ibStart) {
            if (null == input)
                throw new System.ArgumentNullException("input", "Unable convert null array to array of uInts");
            uint[] result = new uint[16];
            for (int i = 0; i < 16; i++) {
                result[i] = (uint)input[ibStart + i * 4];
                result[i] += (uint)input[ibStart + i * 4 + 1] << 8;
                result[i] += (uint)input[ibStart + i * 4 + 2] << 16;
                result[i] += (uint)input[ibStart + i * 4 + 3] << 24;
            }
            return result;
        }

        #endregion
        //
        #region iterator
        /// <summary>
        /// 从目标集合中切取指定索引开始的指定个数的子集
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="start"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public static IEnumerable<T> CutOut<T>(this IEnumerable<T> array, int start, int count) {
            var index = 0;
            foreach (var item in array) {
                if (index >= start && count > 0) {
                    yield return item;
                    count--;
                }
                index++;
            }
        }
        /// <summary>
        /// 集合的长度对割序列
        /// </summary>
        /// <param name="len"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        public static IEnumerable<int> GetLengthHigh(this int len, int p = 2) {
            if (p < 2) p = 2;
            var x = len;
            do {
                yield return x;
                x /= 2;
            } while (x >= 1);
        }
        /// <summary>
        /// 索引2度矩阵结构数据的 行或列
        /// </summary>
        /// <typeparam name="T">数据源</typeparam>
        /// <param name="ms"></param>
        /// <param name="p">行数 或 列数</param>
        /// <param name="roc">row or column</param>
        /// <returns></returns>
        public static IEnumerable<T> This<T>(this T[,] ms, int p, bool roc = true) {
            var row = ms.GetLength(0);
            var col = ms.GetLength(1);
            if (roc) {
                for (int i = 0; i < col; i++) {
                    yield return ms[p, i];
                }
            } else {
                for (int i = 0; i < row; i++) {
                    yield return ms[i, p];
                }
            }
        }
        /// <summary>
        /// 切取三维数据阵列中的某一页数据
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="ms"></param>
        /// <param name="p"></param>
        /// <param name="xyz">？：z=p,true:x=p,false:y=p</param>
        /// <returns></returns>
        public static IEnumerable<T> This<T>(this T[, ,] ms, int p, bool? xyz = null) {
            var x = ms.GetLength(0);
            var y = ms.GetLength(1);
            var z = ms.GetLength(2);
            switch (xyz) {
                case null:
                    for (int i = 0; i < x; i++) {
                        for (int j = 0; j < y; j++) {
                            yield return ms[i, j, p];
                        }
                    }
                    break;
                case true:
                    for (int i = 0; i < y; i++) {
                        for (int j = 0; j < z; j++) {
                            yield return ms[p, i, j];
                        }
                    }
                    break;
                case false:
                    for (int i = 0; i < x; i++) {
                        for (int j = 0; j < z; j++) {
                            yield return ms[i, p, j];
                        }
                    }
                    break;
                default:
                    break;
            }
        }
        public static IEnumerable<B> Filter<A, B>(this IEnumerable<A> xs, Func<A, B> f)
            where A : struct
            where B : struct {
            foreach (var item in xs) {
                yield return f.Invoke(item);
            }
        }
        /// <summary>
        /// 洗牌算法
        /// </summary>
        /// <param name="data"></param>
        public static void Shuffle(this int[] data) {
            var ran = new Random();
            var count = data.Count();
            for (int i = 0; i < count; i++) {
                var x = ran.Next(count);
                var temp = data[i];
                data[i] = data[x];
                data[x] = temp;
            }
        }
        /// <summary>
        /// 获取指定范围的随机不重复整数
        /// </summary>
        /// <typeparam name="T">short or byte</typeparam>
        /// <param name="num">随机数组长度</param>
        /// <param name="max"></param>
        /// <param name="min"></param>
        /// <returns></returns>
        public static IEnumerable<int> UnrepeatSet(this ushort num, int max, int min = 0) {
            if (min < 0 || max < min) {
                throw new Exception("min must greater than zero , or max must greater than min");
            }
            if (num > (max - min) / 2) {
                throw new Exception("num must be less than a half of the maximum minus the minimum");
            }
            var x = from item in max.AdagunSet()
                    where item >= min
                    select item;
            var x2 = x.ToList();
            var ran = new Random();
            for (int i = 0; i < num; i++) {
                var x3 = ran.Next(max - min - i);
                yield return x2[x3];
                x2.Remove(x2[x3]);//利用移除后元素自动连续性重振不留的空位的特性，保持此算法为高效成立的算法。
            }
        }
        /// <summary>
        /// 2次方集合
        /// </summary>
        /// <param name="radix"></param>
        /// <param name="exp"></param>
        /// <returns></returns>
        public static IEnumerable<int> PowerSet(this byte radix, byte exp) {
            if (radix < 0 || exp < 0)
                throw new Exception("input argument is less than zero");
            if (exp > 32) {
                throw new Exception("the argument 'exp' out off the range");
            }
            var result = 1;
            for (int i = 0; i < exp; i++) {
                yield return result *= radix;
            }
        }
        public static IEnumerable<int> EvenSet(this int n) {
            if (n < 0)
                throw new Exception("input argument is less than zero");
            var len = n / 2;
            for (int i = 0; i < len; i++) {
                yield return i * 2;
            }
        }
        public static IEnumerable<int> OddSet(this int n) {
            if (n < 0)
                throw new Exception("input argument is less than zero");
            var len = n / 2;
            for (int i = 0; i < len; i++) {
                yield return i * 2 + 1;
            }
        }
        /// <summary>
        /// 0-n的所有值
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<int> AdagunSet(this int n) {
            if (n < 0)
                throw new Exception("input argument is less than zero");
            for (int i = 0; i < n; i++) {
                yield return i;
            }
        }
        public static int Fibonacci(this int n) {
            if (n < 0)
                throw new Exception("input argument is less than zero");
            if (n == 1 || n == 2) {
                return 1;
            }
            return (Fibonacci(n - 1) + Fibonacci(n - 2));
        }
        public static IEnumerable<int> FibonacciSet(this int n) {
            if (n < 0)
                throw new Exception("input argument is less than zero");
            for (int i = 1; i < n + 1; i++) {
                yield return Fibonacci(i);
            }
        }
        public static IEnumerable<T> GetItem<T>(this Tople<T, T>[] d2Points, byte d = 0) {
            switch (d) {
                case 0:
                    foreach (var item in d2Points) {
                        yield return item.Item1;
                    }
                    break;
                case 1:
                    foreach (var item in d2Points) {
                        yield return item.Item2;
                    }
                    break;
            }
        }
        public static IEnumerable<T> GetItem<T>(this Tople<T, T, T>[] d3Points, byte d = 0) {
            switch (d) {
                case 0:
                    foreach (var item in d3Points) {
                        yield return item.Item1;
                    }
                    break;
                case 1:
                    foreach (var item in d3Points) {
                        yield return item.Item2;
                    }
                    break;
                case 2:
                    foreach (var item in d3Points) {
                        yield return item.Item3;
                    }
                    break;
            }
        }
        #endregion
        //
        #region least squares fit
        /// <summary>
        /// 通过多项式最小二乘计算插入x坐标值的函数值y
        /// </summary>
        /// <param name="equationData">多项式方程系数阵</param>
        /// <param name="x">要插入的x值</param>
        /// <returns>函数值y</returns>
        public static double GetMCValue(this double[] equationData, double x) {
            var r = equationData[0];
            for (int i = 1; i < equationData.Length; i++) {
                r += Math.Pow(x, i) * equationData[i];
            }
            return r;
        }
        public static string ToEquationString(this double[] equationData) {
            var r = string.Empty;
            for (int i = 0; i < equationData.Length; i++) {
                r += string.Format("{0}*x^{1}+", equationData[i].ToString(), i);
            }
            r = r.Substring(0, r.Length - 1);
            r = r.Replace("*x^0", "");
            r = "f(x)=" + r;
            return r;
        }
        /*
         * http://blog.sina.com.cn/s/blog_6e51df7f0100thie.html
         * 星星分享的博客
         */
        ///<summary>
        ///用最小二乘法拟合一元多次曲线
        ///例如：y=a0+a1*x 返回值则为a0 a1
        ///例如：y=a0+a1*x+a2*x*x 返回值则为a0 a1 a2
        ///</summary>
        ///<param name="ps">一组待考查2d坐标点数据集合</param>
        ///<param name="dimension">方程的最高次数</param>
        public static double[] MultiCurveEquation(this Tople<double, double>[] ps, int dimension) {//二元多次线性方程拟合曲线        
            var length = ps.Length;
            var arrX = ps.GetItem().ToArray();
            var arrY = ps.GetItem(1).ToArray();
            int n = dimension + 1;                  //dimension次方程需要求 dimension+1个 系数
            double[,] Guass = new double[n, n + 1];      //高斯矩阵 例如：y=a0+a1*x+a2*x*x
            for (int i = 0; i < n; i++) {
                int j;
                for (j = 0; j < n; j++) {
                    Guass[i, j] = SumArr(arrX, j + i, length);
                }
                Guass[i, j] = SumArr(arrX, i, arrY, 1, length);
            }
            return ComputGauss(Guass, n);
        }
        static double SumArr(double[] arr, int n, int length) { //求数组的元素的n次方的和        
            double s = 0;
            for (int i = 0; i < length; i++) {
                if (arr[i] != 0 || n != 0)
                    s = s + Math.Pow(arr[i], n);
                else
                    s = s + 1;
            }
            return s;
        }
        static double SumArr(double[] arr1, int n1, double[] arr2, int n2, int length) {
            double s = 0;
            for (int i = 0; i < length; i++) {
                if ((arr1[i] != 0 || n1 != 0) && (arr2[i] != 0 || n2 != 0))
                    s = s + Math.Pow(arr1[i], n1) * Math.Pow(arr2[i], n2);
                else
                    s = s + 1;
            }
            return s;
        }
        static double[] ComputGauss(double[,] Guass, int n) {
            int i, j;
            int k, m;
            double temp;
            double max;
            double s;
            double[] x = new double[n];
            for (i = 0; i < n; i++) x[i] = 0.0;//初始化
            for (j = 0; j < n; j++) {
                max = 0;
                k = j;
                for (i = j; i < n; i++) {
                    if (Math.Abs(Guass[i, j]) > max) {
                        max = Guass[i, j];
                        k = i;
                    }
                }
                if (k != j) {
                    for (m = j; m < n + 1; m++) {
                        temp = Guass[j, m];
                        Guass[j, m] = Guass[k, m];
                        Guass[k, m] = temp;
                    }
                }
                if (0 == max) {
                    // "此线性方程为奇异线性方程" 
                    return x;
                }
                for (i = j + 1; i < n; i++) {
                    s = Guass[i, j];
                    for (m = j; m < n + 1; m++) {
                        Guass[i, m] = Guass[i, m] - Guass[j, m] * s / (Guass[j, j]);
                    }
                }
            }//结束for (j=0;j<n;j++)
            for (i = n - 1; i >= 0; i--) {
                s = 0;
                for (j = i + 1; j < n; j++) {
                    s = s + Guass[i, j] * x[j];
                }
                x[i] = (Guass[i, n] - s) / Guass[i, i];
            }
            return x;
        }//返回值是函数的系数
        #endregion
        //
        #region graph
        public static Tople<int, int, float>[] Prim<T>(this Graph<T> g) {
            var r = new List<Tople<int, int, float>>();
            var temp = g[0];//按索引顺序遍历
            HashSet<Graph<T>.Node> hs1, hs2; hs1 = new HashSet<Graph<T>.Node>(); hs2 = new HashSet<Graph<T>.Node>(g.Vertexs);
        nextstep:
            hs1.Add(temp); hs2.Remove(temp);
            var minkey = new Tople<int, float>(0, float.MaxValue);
            foreach (var temps in hs1) {
                foreach (var item in temps.Association) {
                    var x = g.GetEdge(temps.Index, item.Index);
                    var min = x == null ? float.MaxValue : x.Value;
                    if (hs2.Contains(item) && minkey.Item2 > min) {
                        minkey.Item1 = item.Index; minkey.Item2 = min;
                        temp = temps;
                    }
                }
            }
            if (hs2.Count > 0) {
                r.Add(new Tople<int, int, float>(temp.Index, minkey.Item1, minkey.Item2));
                temp = g[minkey.Item1];
                goto nextstep;
            }
            return r.ToArray();
        }
        public static Tople<int, int, float>[] Kruscal<T>(this Graph<T> g) {//K​r​u​s​k​a​l
            var r = new List<Tople<int, int, float>>();
            var us = g.UnionSet();//构造并查集
            var sides = g.SideOrder();//把所有边按权由小到大排序 <int,int,float>的方式返回前两个int为顶点索引
            var count = g.Count - 1;//达到边减1即找到所需要的最小生成树
            for (int i = 0; i < sides.Length; i++) {
                if (us.FindUionSetRoot(sides[i].Item1) == us.FindUionSetRoot(sides[i].Item2))
                    continue;
                us.Connect(sides[i].Item1, sides[i].Item2);
                if (r.Count == count) break;
                r.Add(sides[i]);
            }
            return r.ToArray();
        }
        public static Tople<int, int, float>[] SideOrder<T>(this Graph<T> g) {
            var r = new List<Tople<int, int, float>>();
            for (int i = 0; i < g.Sides.Length; i++) {
                for (int j = 0; j < g.Sides[i].Count; j++) {
                    r.Add(new Tople<int, int, float>(i, g.Sides[i][j].Item1, g.Sides[i][j].Item2));
                }
            }
            return (from item in r orderby item.Item3 select item).ToArray();
        }
        public static int[] UnionSet<T>(this Graph<T> g) {
            var count = g.Count;
            var r = new int[count];
            for (int i = 0; i < count; i++) {
                if (g[i] != null) r[i] = g[i].Index;
            }
            return r;
        }
        //采用较小为根的策略
        static public void Connect(this int[] unionset, int n1, int n2) {
            if (unionset.FindUionSetRoot(n1) == unionset.FindUionSetRoot(n2)) return;
            unionset[n1 < n2 ? n2 : n1] = n1 < n2 ? n1 : n2;
        }
        /// <summary>
        /// 为什么有Find算法？ 因为while在预设的情况下 不是死循环
        /// </summary>
        /// <param name="unionset"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        static public int FindUionSetRoot(this int[] unionset, int p) {
            int r = p, t; while (unionset[r] != r) r = unionset[r]; //这步已经找到了根可返回
            while (p != r) { t = unionset[p]; unionset[p] = r; p = t; }//这步是所谓压缩并查集的查找路径,把查找路径上的所有长连全部直接接到根上
            return r;
        }
        #endregion
        //
        #region io
        /// <summary>
        /// copy stream to memory stream then get it byte[]
        /// </summary>
        /// <param name="s"></param>
        /// <param name="target">usually it is a memory stream</param>
        public static void CopyStreamTo(this Stream s, Stream target) {
            var reader = new BinaryReader(s);
            var writer = new BinaryWriter(target);
            writer.Seek((int)target.Length, SeekOrigin.Begin);
            byte[] buffer = null;
            do {
                buffer = reader.ReadBytes(256);
                writer.Write(buffer);
            } while (buffer.Length > 0);
            writer.Flush();
        }
        #endregion
        //
        #region type
        static IEnumerable<string> GetStandardTypeName_Help(Type t) {
            var x = t.GetGenericArguments();
            if (x.Length > 0) {
                yield return t.Name.Split('`')[0];
                yield return "<";
                foreach (var item in x) {
                    foreach (var item2 in GetStandardTypeName_Help(item)) { yield return item2; }
                }
                yield return ">";
            } else {
                yield return t.Name;
            }
        }
        static public string GetStandardTypeName(this Type t) {
            var x = GetStandardTypeName_Help(t);
            var x2 = x.ToArray();
            var x3 = string.Join(",", x2);
            var x4 = x3.Replace(",<,", "<");
            return x4.Replace(",>", ">");
        }
        #endregion
    }
    #region md5
    struct ABCDStruct { public uint A; public uint B; public uint C; public uint D;}
    #endregion
}
